#include <bits/stdc++.h>
using namespace std;

/*
2338. 统计理想数组的数目
已解答
困难
相关标签
相关企业
提示
给你两个整数 n 和 maxValue ，用于描述一个 理想数组 。

对于下标从 0 开始、长度为 n 的整数数组 arr ，如果满足以下条件，则认为该数组是一个 理想数组 ：

每个 arr[i] 都是从 1 到 maxValue 范围内的一个值，其中 0 <= i < n 。
每个 arr[i] 都可以被 arr[i - 1] 整除，其中 0 < i < n 。
返回长度为 n 的 不同 理想数组的数目。由于答案可能很大，返回对 109 + 7 取余的结果。

 

示例 1：

输入：n = 2, maxValue = 5
输出：10
解释：存在以下理想数组：
- 以 1 开头的数组（5 个）：[1,1]、[1,2]、[1,3]、[1,4]、[1,5]
- 以 2 开头的数组（2 个）：[2,2]、[2,4]
- 以 3 开头的数组（1 个）：[3,3]
- 以 4 开头的数组（1 个）：[4,4]
- 以 5 开头的数组（1 个）：[5,5]
共计 5 + 2 + 1 + 1 + 1 = 10 个不同理想数组。
示例 2：

输入：n = 5, maxValue = 3
输出：11
解释：存在以下理想数组：
- 以 1 开头的数组（9 个）：
   - 不含其他不同值（1 个）：[1,1,1,1,1] 
   - 含一个不同值 2（4 个）：[1,1,1,1,2], [1,1,1,2,2], [1,1,2,2,2], [1,2,2,2,2]
   - 含一个不同值 3（4 个）：[1,1,1,1,3], [1,1,1,3,3], [1,1,3,3,3], [1,3,3,3,3]
- 以 2 开头的数组（1 个）：[2,2,2,2,2]
- 以 3 开头的数组（1 个）：[3,3,3,3,3]
共计 9 + 1 + 1 = 11 个不同理想数组。
 

提示：

2 <= n <= 104
1 <= maxValue <= 104
*/

// 法一
const int MOD = 1e9 + 7;
const int MAX_N = 1e4 + 10;   // 最大元素值（根据题目约束调整）
const int MAX_P = 15;         // 最大质因数个数（log2(1e4)=14，取15足够）

// 使用 long long 防止组合数计算溢出
long long c[MAX_N + MAX_P][MAX_P + 1];  // 组合数数组
vector<int> ps[MAX_N];        // 存储每个数的质因数次数
int sieve[MAX_N];             // 最小质因数筛

class Solution {
public:
    Solution() {
        if (c[0][0]) return;  // 确保只初始化一次
        
        // 埃拉托斯特尼筛法求最小质因数
        for (int i = 2; i < MAX_N; ++i) {
            if (!sieve[i]) {  // i是质数
                for (int j = i; j < MAX_N; j += i) {
                    if (!sieve[j]) sieve[j] = i;  // 记录最小质因数
                }
            }
        }

        // 预处理每个数的质因数分解[7]
        for (int i = 2; i < MAX_N; ++i) {
            int x = i;
            while (x > 1) {
                int p = sieve[x], cnt = 0;
                while (x % p == 0) {
                    x /= p;
                    ++cnt;
                }
                ps[i].push_back(cnt);  // 记录质因数p的次数
            }
        }

        // 组合数递推计算（模运算防溢出）
        c[0][0] = 1;
        for (int i = 1; i < MAX_N + MAX_P; ++i) {
            c[i][0] = 1;  // C(n,0)=1
            for (int j = 1; j <= min(i, MAX_P); ++j) {
                // 使用 long long 防止中间结果溢出
                c[i][j] = (c[i-1][j] + c[i-1][j-1]) % MOD;
            }
        }
    }

    int idealArrays(int n, int maxValue) {
        long long ans = 0;
        for (int x = 1; x <= maxValue; ++x) {  // 遍历所有可能的末位元素
            long long mul = 1;
            // 分解x的质因数（已预计算）
            for (int cnt : ps[x]) { 
                // 组合数公式：C(n-1 + cnt, cnt)
                mul = (mul * c[n-1 + cnt][cnt]) % MOD; 
            }
            ans = (ans + mul) % MOD;
        }
        return ans;
    }
};

// 法二
const int MOD = 1'000'000'007;        // 模数
const int MAX_N = 10'000;             // 处理的最大数值
const int MAX_E = 13;                 // 质因数分解后的最大指数（log2(10000) ≈ 13）

vector<int> EXP[MAX_N + 1];           // EXP[x]存储x的质因数分解后的各个指数
int C[MAX_N + MAX_E][MAX_E + 1];      // 组合数C(i,j)的值

// 预处理质因数分解和组合数，程序启动时自动执行
int init = []() {
    // 预处理每个数的质因数分解指数
    for (int x = 2; x <= MAX_N; x++) {
        int t = x;
        // 试除法分解质因数
        for (int i = 2; i * i <= t; i++) {
            int e = 0; // 当前质因数i的指数
            while (t % i == 0) {
                e++;
                t /= i;
            }
            if (e > 0) {
                EXP[x].push_back(e); // 记录质因数i的指数
            }
        }
        // 处理剩余的质因数（例如t是质数）
        if (t > 1) {
            EXP[x].push_back(1); // 指数为1
        }
    }

    // 预处理组合数C(n + e - 1, e)的值
    for (int i = 0; i < MAX_N + MAX_E; i++) {
        C[i][0] = 1; // C(i,0)=1
        // 递推计算组合数C(i,j) = C(i-1,j) + C(i-1,j-1)
        for (int j = 1; j <= min(i, MAX_E); j++) {
            C[i][j] = (C[i - 1][j] + C[i - 1][j - 1]) % MOD;
        }
    }
    return 0;
}();

class Solution {
public:
    int idealArrays(int n, int maxValue) {
        long long ans = 0;
        // 遍历所有可能的数组最后一个元素x
        for (int x = 1; x <= maxValue; x++) {
            long long res = 1;
            // 遍历x的质因数分解后的各个指数e
            for (int e : EXP[x]) {
                // 计算贡献：将n个元素分为e个递增步骤，组合数为C(n+e-1, e)
                res = res * C[n + e - 1][e] % MOD;
            }
            ans = (ans + res) % MOD; // 累加结果
        }
        return ans % MOD;
    }
};

// 法三
int mod = 1e9 + 7;
vector<int> isp(10015, false);
vector<int> p;
vector<vector<int>> ps(10015);
int C[10015][16] = {}; // 尽量够大，n ≤ 10000，质因子指数最多十几
int init = []() {
    for (int i = 0; i < 10015; i++) {
        C[i][0] = 1;
        for (int j = 1; j <= min(i, 15); j++) {
            C[i][j] = (C[i - 1][j] + C[i - 1][j - 1]) % mod;
        }
    }
    for (int i = 2; i < 10015; i++) {
        if (!isp[i]) {
            for (int j = i; j < 10015; j += i) {
                isp[j] = 1;
                ps[j].push_back(i);
            }
        }
    }
    return 0;
}();
class Solution {
public:
    int idealArrays(int n, int maxValue) {
        // 素数筛与因式分解同时进行，欧拉筛只会记录最大因数
        int ans = 0;
        for (int i = 1; i <= maxValue; i++) // 以每个数结尾的个数
        {
            int ans_temp = 1;
            int temp = i;
            for (auto& j : ps[i]) {
                int sum = 0;
                while (temp % j == 0) {
                    sum++;
                    temp /= j;
                }
                ans_temp = 1LL * ans_temp * C[n + sum - 1][sum] % mod;
            }
            ans = (ans + ans_temp) % mod;
        }
        return ans;
    }
};